/**
 *  filename:   find_kth.c
 *  author:     大梦
 *  date:       2015/4/8
 *  desc:       LeetCode-OJ 2-5
 *              2.1.5 Median of Two Sorted Arrays
 *  history:
 *              2015/4/8 create the file
 */

#include <stdio.h>

#define min(X,Y) ((X) < (Y) ? (X) : (Y))

int find_kth(int A[], int m, int B[], int n, int k)
{
    /* assume A is always shorter than B */
    if (m > n) return find_kth(B, n, A, m, k);

    /* A or B is empty */
    if (m == 0) return B[k-1];

    /* if K=1, return the minimum element of A and B */
    if (k == 1) return min(A[0], B[0]);

    /* divide k into two part */
    int ia = min(m, k/2);
    int ib = k - ia;

    /* if equal, is the kth value */
    if (A[ia - 1] == B[ib - 1]) return A[ia - 1];

    /* drop B[0] - B[ib-1] */
    if (A[ia - 1] > B[ib - 1]) {
        return find_kth(A, m, B+ib, n-ib, k-ib);
    } else { /* drop A[0] - A[ia-1] */
        return find_kth(A+ia, m-ia, B, n, k-ia);
    }
}

int main()
{
    int m = 3;
    int n = 9;
    double mid = 0.0;
    int A[3] = {1,2,3};
    int B[9] = {3,4,5,6,7,8,9,10,11};

    if ((m+n)%2 != 0) {
        mid = (double)find_kth(A, m, B, n, (m+n)/2);
    } else {
        double mid1 = (double)find_kth(A, m, B, n, (m+n)/2);
        double mid2 = (double)find_kth(A, m, B, n, (m+n)/2+1);
        mid =(mid1 + mid2)/2;
    }

    printf("the median number is: %lf\n", mid);

    return 0;
}

#if 0
There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted
arrays. The overall run time complexity should be O(log(m + n)).
#endif // 0
